package com.gyg.程序员面试金典;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode(int x) {
 * val = x;
 * next = null;
 * }
 * }
 */

import java.util.Stack;

/**
 * 面试题 02.07. 链表相交
 */
public class T02_07 {


    /**
     * 正确解法
     *  判断内存地址是否相等
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode_0(ListNode headA, ListNode headB) {
//        （1）、由于不能破坏原链表的结构，所以使用参数传递，用一个新的链表代替原来的链表
        ListNode tempHeadA = headA;
        ListNode tempHeadB = headB;
//        （2）、循环遍历两个链表，让他们走过相同长度的节点，
//        （3）、直到两个链表最后都指向同一个相交节点的内存地址，此时tempHeadA和tempHeadB走过的节点是相同的，（顺序不同）
//        当tempHeadA和tempHeadB指向的内存地址相同的时候，说明都该指向相交的节点了
        while (tempHeadA != tempHeadB){
//        （4）、让tempHeadA先走完自身的节点，再遍历HeadB
            tempHeadA = tempHeadA==null?headB:tempHeadA.next;
//        （5）、让tempHeadB先走完自身的节点，再遍历HeadA
            tempHeadB = tempHeadB==null?headA:tempHeadB.next;
        }
//        （6）、此时tempHeadA和tempHeadB指向的都是相交部分的第一个节点，所以返回tempHeadA或tempHeadB都可以
        return tempHeadA;
    }

    /**
     * 错误解法
     * 使用stack堆栈对值判断的，
     * 错误思想，应该是对内存地址判断
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode tempHeadA = headA;
        ListNode tempHeadB = headB;
        int m, n;
        Stack<Integer> stackA = new Stack<Integer>();
        Stack<Integer> stackB = new Stack<Integer>();
        while (tempHeadA != null) {
            stackA.add(tempHeadA.val);
            tempHeadA = tempHeadA.next;
        }
        while (tempHeadB != null) {
            stackB.add(tempHeadB.val);
            tempHeadB = tempHeadB.next;
        }
        int minCount = stackA.size() > stackB.size() ? stackB.size() : stackA.size();
        ListNode result = null;
        for (int i = 0; i < minCount; i++) {
            if (!stackA.peek().equals(stackB.peek())) {
                if (i == 0) {
                    return null;
                } else {
                    return result;
                }
            }
            ListNode tempNode = new ListNode(0);
            tempNode.val = stackA.peek();
            tempNode.next = result;
            result = tempNode;
            stackA.pop();
            stackB.pop();
        }
        return result;
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}
